package com.jia.interviewPro;

/**
 * @program: Leetcode
 * @description: https://leetcode-cn.com/problems/three-steps-problem-lcci/
 * @author: STU756
 * @create: 2020-09-03 11:03
 */
public class Pro0801 {
    public int waysToStep2(int n) {
        if(n <= 2) return n;
        if(n == 3) return 4;
        long[] f = new long[n+1];
        f[0] = 0;
        f[1] = 1;
        f[2] = 2;
        f[3] = 4;
        for(int i = 4; i <= n; i++) {
            f[i] = f[i-1] + f[i-2] + f[i-3];
            f[i] %= 1000000007;
        }
        return (int)f[n];
    }
    public int waysToStep(int n) {
        if(n <= 2) return n;
        if(n == 3) return 4;
        long f1 = 1;
        long f2 = 2;
        long f3 = 4;
        for(int i = 4; i <= n; i++) {
            long tmp = f3;
            f3 = (f3 + f1 + f2) % 1000000007;
            f1 = f2;
            f2 = tmp;
        }
        return (int) f3;
    }
}
